package com.zjj.learn.algorithmPlus.segment1.priorityQueue;

import com.zjj.learn.algorithmPlus.segment1.queue.Queue;


/**
 * 堆一般看做一个完全二叉树
 * 优先级队列使用大根堆更加合适，即每一个节点的值不小于孩子节点。
 * 因为优先级队列每一个获取都是获取优先级最高的数据，所以使用大根堆更加方便。
 *
 * @author zjj_admin
 */
public class HeapPriorityQueue<E extends Priority> implements Queue<E> {


    private final E[] array;
    private int size;

    @SuppressWarnings("all")
    public HeapPriorityQueue(int capacity) {
        size = 0;
        array = (E[]) new Priority[capacity];
    }

    /**
     * 添加数据
     * 步骤：
     * 1、将新添加的元素存在完全二叉树的最后一个节点
     * 2、调整堆的结构让其满足大根堆的特点
     *
     * @param value 添加数据
     * @return
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        if (size == 0) {
            array[size] = value;
            size++;
            return true;
        }
        //获取添加节点的索引
        int addIndex = size;
        size++;
        //获取父节点的索引
        int parentIndex = (addIndex - 1) / 2;
        //对堆的结构进行调整，让其满足大根堆的特性。
        while (addIndex > 0 && array[parentIndex].priority() < value.priority()) {
            array[addIndex] = array[parentIndex];
            addIndex = parentIndex;
            parentIndex = (addIndex - 1) / 2;
        }
        array[addIndex] = value;

        return true;
    }


    /**
     * 移除并返回优先级最高的一个数据
     * 步骤：
     * 1、获取第一个数据，第一个数据及时需要移除的数据。
     * 2、将第一个数据和最后一个数据进行交换，让需要移除的数据放在数组的最后面。
     * 3、将堆的最后一个数据移除
     * 4、将根节点按照大根堆的特点调整位置，让其满足大根堆。
     *
     * @return
     */
    @SuppressWarnings("all")
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        //获取需要移除的位置
        E removed = array[0];
        //将数组的长度减少一个单位
        size--;
        //将最后一个放在第一个位置
        array[0] = array[size];
        //将最后一个数据设置为 null ，方便垃圾回收
        array[size] = null;
        //调整，是指满足大根堆的条件，做下潜操作
        down(0);
        return removed;
    }

    /**
     * 下潜操作，知道满足大根堆的条件
     *
     * @param index
     */
    private void down(int index) {
        if (2 * index + 1 < size && array[index].priority() < array[2 * index + 1].priority()) {
            // 交换位置
            exchange(index, 2 * index + 1);
            // 做下潜操作
            down(2 * index + 1);
        } else if (2 * index + 2 < size && array[index].priority() < array[2 * index + 2].priority()) {
            // 交换位置
            exchange(index, 2 * index + 2);
            // 做下潜操作
            down(2 * index + 2);
        }
    }

    /**
     * 交换索引 i 和索引 j
     *
     * @param i
     * @param j
     */
    private void exchange(int i, int j) {
        E temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


    /**
     * 返回优先级最高的一个数据
     *
     * @return
     */
    @SuppressWarnings("all")
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    @Override
    public int size() {
        return size;
    }

}
